/**
 * 45.跳跃游戏II
 */
public class Exerciser7 {
    /**
     * 贪心算法
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        // 贪心：
        // 类似于层序遍历的过程
        int n = nums.length;
        int left = 0,right = 0;
        int maxPos = 0;
        int ret = 0;
        while(left <= right) {
            if(maxPos >= n - 1) {
                // 进行判断是否已经跳跃到了最后一个位置了
                return ret;
            }
            // 遍历 left 和 right 区间的值 进行跳跃
            for(int i = left;i <= right;i++) {
                maxPos = Math.max(maxPos,nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
            ret++;
        }
        return -1;
    }

    /**
     * 动态规划
     * @param nums
     * @return
     */
    public int jump1(int[] nums) {
        int n = nums.length;
        // dp[i]: 表示从0位置开始，到达i位置的时候的最小跳跃值
        int[] dp = new int[n];
        for(int i = 0;i < n;i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for(int i = 1;i < n;i++) {
            for(int j = 0;j < i;j++) {
                if(nums[j] + j >= i) {
                    dp[i] = Math.min(dp[j] + 1,dp[i]);
                }
            }
        }
        return dp[n - 1];
    }
}
